﻿
小明是学校里的一名老师，他带的班级共有 n 名同学，第 i 名同学力量值为 a
i
​
。在闲暇之余，小明决定在班级里组织一场拔河比赛。
两个队伍的人数不必相同，但是需要让队伍内的同学们的力量值之和尽可能相近。请计算出力量值之和差距最小的挑选队伍的方式。

输出共一行，一个非负整数，表示两个队伍力量值之和的最小差距。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
vector<long long>sum;
vector<pair<long long, pair<int, int>>>lr;
void solve() {
    int n;
    cin >> n;
    sum.resize(n + 1);
    //求出前缀和：
    for (int i = 1; i <= n; i++) {
        long long data;
        cin >> data;
        sum[i] = sum[i - 1] + data;
    }
    //所有区间：
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            lr.push_back({ sum[j] - sum[i - 1],{i,j} });
        }
    }
    //筛选出符合要求的：
    //不重叠不相交区间：注意排序时候区间相对下标位置的变化
    sort(lr.begin(), lr.end());
    long long ret = LLONG_MAX;
    for (int i = 0; i < lr.size() - 1; i++) {
        if (lr[i].second.second < lr[i + 1].second.first ||
            lr[i + 1].second.second < lr[i].second.first)
            ret = min(ret, lr[i + 1].first - lr[i].first);
    }
    cout << ret << endl;
}
int main() {
    solve();
    return 0;
}